package com.剑指offer.第二章;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入一个整数数组和一个整数k，请问数组中有多少个数字之和等于k的连续子数组？例如：输入数组[1,1,1] k的值为2 有两个连续的子数组之后等于2
 */
public class 累加数组数字求子数组之和 {

    /**
     * 当扫描数组的第i个数字并求得前i个数字之和是x时，需要知道在i之前存在多少个j并且前j个数字之和等于x-k。
     *
     * @param nums
     * @param k
     * @return
     */
    public static int resolve(int[] nums, int k) {
        Map<Integer, Integer> sumToCount = new HashMap<Integer, Integer>();

        sumToCount.put(0, 1);

        int sum = 0;
        int count = 0;
        for (int num : nums) {
            sum += num;
            count += sumToCount.getOrDefault(sum - k, 0);
            sumToCount.put(sum, sumToCount.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(resolve(new int[]{-1, 1, -1, 1}, 0));
    }

}
